home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / ldb.zip / BINDER.CPP < prev    next >
C/C++ Source or Header  |  1991-10-18  |  13KB  |  685 lines
  1. /*
  2.  
  3.     binder.cpp
  4.     10-18-91
  5.     Loose Data Binder v 1.4
  6.  
  7.     Copyright 1991
  8.     John W. Small
  9.     All rights reserved
  10.  
  11.     PSW / Power SoftWare
  12.     P.O. Box 10072
  13.     McLean, Virginia 22102 8072 USA
  14.  
  15.     John Small
  16.     Voice: (703) 759-3838
  17.     CIS: 73757,2233
  18.  
  19. */
  20.  
  21.  
  22. #include <string.h>
  23. #include "binder.hpp"
  24.  
  25. void Binder::construct(unsigned flags, unsigned maxNodes,
  26.     unsigned limit, unsigned delta)
  27. {
  28.     curNode = first = nodes = 0;
  29.     comparE = BDRcomparE0;
  30.  
  31. /*
  32.     The following relationships are maintained
  33.     during operation of a binder:
  34.  
  35.     1 <= delta <= lowLimit <= limit <= maxNodes
  36.         <= BDR_MAXNODES
  37.     lowThreshold = lowLimit - delta;
  38. */
  39.  
  40.     if (maxNodes > BDR_MAXNODES)
  41.         maxNodes = BDR_MAXNODES;
  42.     if (limit > maxNodes)
  43.         limit = maxNodes;
  44.     if (delta > limit)
  45.         delta = limit;
  46.     if (!delta)  {
  47.         delta = 1;
  48.         if (limit < delta)
  49.             limit = delta;
  50.         if (maxNodes < limit)
  51.             maxNodes = limit;
  52.     }
  53.     if ((linkS = new voiD[limit]) == voiDV0)
  54.         this->limit = lowLimit = lowThreshold
  55.             = this->delta = this->maxNodes
  56.             = this->flags = 0;
  57.     else  {
  58.         this->limit = limit;
  59.         this->delta = delta;
  60.         this->maxNodes = maxNodes;
  61.         lowLimit = limit;
  62.         lowThreshold = lowLimit - delta;
  63.         this->flags = ((flags & BDR_OK_FREE) 
  64.             | BDR_SORTED);
  65.     }
  66. }
  67.  
  68. Binder::Binder(voiDV argv, int argc, unsigned flags)
  69. {
  70.     construct(flags,BDR_MAXNODES,argc,BDR_DELTA);
  71.     if (argv) if (argc > 0)
  72.         while (argc--)
  73.             push(argv[argc]);
  74.     else
  75.         for (argc = 0; insQ(argv[argc]); argc++);
  76. }
  77.  
  78. voiDV Binder::vector()
  79. {
  80.     voiDV V = voiDV0;
  81.  
  82.     if (nodes) if ((V = new voiD[nodes+1]) != voiDV0)  {
  83.         for (unsigned i = 0; i < nodes; i++)
  84.             V[i] = atGet(i);
  85.         V[i] = voiD0;
  86.     }
  87.     return V;
  88. }
  89.  
  90. Binder::~Binder()
  91. {
  92.     if (flags & BDR_OK_FREE)
  93.         allFree();
  94.     else
  95.         allDel();
  96.     if (linkS)
  97.         delete linkS;
  98. }
  99.  
  100. unsigned Binder::setLimit(unsigned newLimit)
  101. {
  102.     voiDV newLinkS;
  103.     unsigned i;
  104.  
  105.     if (newLimit < nodes)
  106.         newLimit = nodes;
  107.     else if (newLimit > maxNodes)
  108.         newLimit = maxNodes;
  109.     if (newLimit < delta)
  110.         newLimit = delta;
  111.     if (!linkS || !newLimit || newLimit == limit)
  112.         return 0;
  113.     if ((newLinkS = new voiD[newLimit]) == voiDV0)
  114.         return 0;
  115.     if ((i = limit - first) > nodes)
  116.         i = nodes;
  117.     memcpy(newLinkS,&linkS[first],sizeof(linkS[0])*i);
  118.     /* copy wrap around */
  119.     if (i < nodes)
  120.         memcpy(&newLinkS[i],linkS,
  121.             sizeof(linkS[0])*(nodes-i));
  122.     if (newLimit > limit)
  123.         if (newLimit - delta > limit)
  124.             lowLimit = newLimit - delta;
  125.         else
  126.             lowLimit = limit;
  127.     else
  128.         if (newLimit - delta > delta)
  129.             lowLimit = newLimit - delta;
  130.         else
  131.             lowLimit = delta;
  132.     lowThreshold = lowLimit - delta;
  133.     delete linkS;
  134.     linkS = newLinkS;
  135.     limit = newLimit;
  136.     first = 0;
  137.     return limit;
  138. }
  139.  
  140. unsigned Binder::setDelta(unsigned newDelta)
  141. {
  142.     return ((newDelta && newDelta <= lowLimit)?
  143.         delta = newDelta : 0);
  144. }
  145.  
  146. unsigned Binder::setMaxNodes(unsigned newMaxNodes)
  147. {
  148.     return ((newMaxNodes >= limit)?
  149.         (maxNodes = (newMaxNodes
  150.         > BDR_MAXNODES)? BDR_MAXNODES
  151.         : newMaxNodes) : 0);
  152. }
  153.  
  154. voiD Binder::atIns(unsigned n, const voiD D)
  155. {
  156.     voiDV newLinkS;
  157.     unsigned newLimit, i;
  158.  
  159.     if (!linkS || !D)
  160.         return voiD0;
  161.     if (nodes == limit)  {
  162.         if (limit == maxNodes)
  163.             return voiD0;
  164.         newLimit = (maxNodes - delta > limit)?
  165.             limit + delta : maxNodes;
  166.         if ((newLinkS = new voiD[newLimit])
  167.             == voiDV0) return voiD0;
  168.         if ((i = limit - first) > nodes)
  169.             i = nodes;
  170.         memcpy(newLinkS,&linkS[first],
  171.             sizeof(linkS[0])*i);
  172.         /* copy wrap around */
  173.         if (i < nodes)
  174.             memcpy(&newLinkS[i],linkS,
  175.                 sizeof(linkS[0])*(nodes-i));
  176.         /*
  177.             Compute next smaller linkS size
  178.             and threshold for shrinking.
  179.         */
  180.         lowLimit = limit;
  181.         lowThreshold = lowLimit - delta;
  182.         /* swap new for old */
  183.         delete linkS;
  184.         linkS = newLinkS;
  185.         limit = newLimit;
  186.         first = 0;
  187.     }
  188.     if (!Dattach(D))
  189.         return voiD0;
  190.     if (!n)  /* push */
  191.         linkS[first? --first
  192.             : (first = limit - 1)] = D;
  193.     else if (n >= nodes) /* insQ */
  194.         linkS[(first+(n=nodes))%limit] = D;
  195.     else  { /* insert interior */
  196.         i = (first + n) % limit;
  197.         if (i < first || !first)
  198.             /* move rear rightward */
  199.             memmove(&linkS[i+1],&linkS[i],
  200.                 sizeof(linkS[0])
  201.                 * (nodes-n));
  202.         else /* move front leftward */
  203.             memmove(&linkS[--first],&linkS[--i],
  204.                 sizeof(linkS[0])*(n+1));
  205.         linkS[i] = D;
  206.     }
  207.     nodes++;
  208.     if (n <= curNode)
  209.         curNode++;
  210.     flags &= ~BDR_SORTED;
  211.     return D;
  212. }
  213.  
  214. voiD Binder::atDel(unsigned n)
  215. {
  216.     voiDV newLinkS;
  217.     unsigned newLimit, i;
  218.     voiD D;
  219.  
  220.     if (!linkS || n >= nodes)
  221.         return voiD0;
  222.     D = linkS[(first+n)%limit];
  223.     if (!n)  {  /* pop */
  224.         if (++first >= limit)
  225.             first = 0;
  226.     }
  227.     else if (n != nodes-1)  {  /* del interior */
  228.         /* move front rightward */
  229.         memmove(&linkS[first+1],&linkS[first],
  230.             sizeof(linkS[0])*n);
  231.         first++;
  232.     }
  233.     if (--nodes == 0)
  234.         flags |= BDR_SORTED;
  235.     if (n < curNode)
  236.         curNode--;
  237.     else if (n == curNode)
  238.         curNode = nodes;
  239.     if (nodes < lowThreshold)  {
  240.         newLimit = lowLimit;
  241.         if ((newLinkS = new voiD[newLimit])
  242.             != voiDV0)  {
  243.             if ((i = limit - first) > nodes)
  244.                 i = nodes;
  245.             memcpy(newLinkS,&linkS[first],
  246.                 sizeof(linkS[0])*i);
  247.             /* copy wrap around */
  248.             if (i < nodes)
  249.                 memcpy(&newLinkS[i],linkS,
  250.                     sizeof(linkS[0])
  251.                     *(nodes-i));
  252.             /*
  253.                 Compute next smaller linkS
  254.                 size and threshold for 
  255.                 shrinking.
  256.             */
  257.             if (lowLimit - delta > delta)
  258.                 lowLimit -= delta;
  259.             else
  260.                 lowLimit = delta;
  261.             lowThreshold = lowLimit - delta;
  262.             /* swap new for old */
  263.             delete linkS;
  264.             linkS = newLinkS;
  265.             limit = newLimit;
  266.             first = 0;
  267.         }
  268.     }
  269.     Ddetach(D);
  270.     return D;
  271. }
  272.  
  273. int Binder::allDel()
  274. {
  275.     if (!linkS)
  276.         return 0;
  277.     for (unsigned i = 0; i < nodes; /* no reinit */)
  278.         if (!atDel(i))
  279.             i++;
  280.     return (nodes? 0 : 1);
  281. }
  282.  
  283. int Binder::allFree()
  284. {
  285.     if (!linkS)
  286.         return 0;
  287.     if (flags & BDR_OK_FREE)
  288.         for (unsigned i = 0; i < nodes; 
  289.             /* no reinit */)
  290.             if (!Dfree(atDel(i)))
  291.                 i++;
  292.     return (nodes? 0 : 1);
  293. }
  294.  
  295. voiD Binder::atPut(unsigned n, const voiD D)
  296. {
  297.     if (linkS && D && (n < nodes))
  298.         if (Dattach(D))  {
  299.             flags &= ~BDR_SORTED;
  300.             voiD& N = linkS[(first+n)%limit];
  301.             Ddetach(N);
  302.             DFREE(N);
  303.             return (N=D);
  304.         }
  305.     return voiD0;
  306. }
  307.  
  308. voiD Binder::atGet(unsigned n)
  309. {
  310.     return ((linkS && (n < nodes))?
  311.         linkS[(first+n)%limit] : voiD0);
  312. }
  313.  
  314. voiD Binder::atXchg(unsigned n, const voiD D)
  315. {
  316.     if (linkS && D && (n < nodes))
  317.         if (Dattach(D))  {
  318.             flags &= ~BDR_SORTED;
  319.             voiD& N = linkS[(first+n)%limit];
  320.             voiD oldD = N;
  321.             N = D;
  322.             Ddetach(oldD);
  323.             return oldD;
  324.         }
  325.     return voiD0;
  326. }
  327.  
  328. unsigned Binder::index(const voiD D)
  329. {
  330.     unsigned i;
  331.  
  332.     if (linkS && D)
  333.         for (i = 0; i < nodes; i++)
  334.             if (D == linkS[(first+i)%limit])
  335.                 return i;
  336.     return BDR_NOTFOUND;
  337. }
  338.  
  339. int Binder::forEach(BDRforEachBlocK B, voiD M, voiD A)
  340. {
  341.     unsigned i;
  342.  
  343.     if (!linkS || !B || !nodes)
  344.         return 0;
  345.     for (i = 0; i < nodes; i++)
  346.         (*B)(linkS[(first+i)%limit],M,A);
  347.     return 1;
  348. }
  349.  
  350. unsigned Binder::firstThat(BDRdetectBlocK B, voiD M)
  351. {
  352.     unsigned i;
  353.  
  354.     if (linkS && B)
  355.         for (i = 0; i < nodes; i++)
  356.             if ((*B)(linkS[(first+i)%limit],M))
  357.                 return i;
  358.     return BDR_NOTFOUND;
  359. }
  360.  
  361. unsigned Binder::lastThat(BDRdetectBlocK B, voiD M)
  362. {
  363.     unsigned i;
  364.  
  365.     if (linkS && B && nodes)
  366.         for (i = nodes; i--; /* no reinit */)
  367.             if ((*B)(linkS[(first+i)%limit],M))
  368.                 return i;
  369.     return BDR_NOTFOUND;
  370. }
  371.  
  372. int Binder::collect(BDRcollectBlocK B, BindeR R,
  373.     voiD M, voiD A)
  374. {
  375.     unsigned i;
  376.  
  377.     if (!linkS || !B || !R)
  378.         return 0;
  379.     for (i = 0; i < nodes; i++)
  380.         (*B)(linkS[(first+i)%limit],R,M,A);
  381.     return 1;
  382. }
  383.  
  384.  
  385. /*  FlexList like primitives:  */
  386.  
  387. unsigned Binder::CurNode()
  388. {
  389.     return ((curNode < nodes)?
  390.         curNode : BDR_NOTFOUND);
  391. }
  392.  
  393. int  Binder::setCurNode(unsigned n)
  394. {
  395.     return ((curNode = ((n > nodes)? nodes : n))
  396.         < nodes);
  397. }
  398.  
  399. Binder& Binder::operator<<(Binder& (*manipulator)
  400.         (Binder& B))
  401. {
  402.     return (manipulator? (*manipulator)(*this)
  403.         : *this);
  404. }
  405.  
  406. voiD Binder::ins(const voiD D)
  407. {
  408.     if (atIns(curNode+1,D))  {
  409.         if (++curNode >= nodes)
  410.             curNode = nodes - 1;
  411.         return D;
  412.     }
  413.     return voiD0;
  414. }
  415.  
  416. voiD Binder::insSort(const voiD D)
  417. {
  418.     unsigned low, mid, high;
  419.     voiD ok;
  420.  
  421. /*
  422.     The current node is left undefined if
  423.     anything fails, otherwise it is set to the
  424.     newly inserted node.
  425. */
  426.  
  427.     curNode = nodes;
  428.     if (!linkS || !D || nodes >= maxNodes || !comparE)
  429.         return voiD0;
  430.     if (!(flags & BDR_SORTED))
  431.         if (!sort())
  432.             return voiD0;
  433.     low = 0;
  434.     high = nodes;
  435.     while (low < high)  {
  436.         mid = low + ((high - low) >> 1);
  437.         if ((*comparE)(D,
  438.             linkS[(first+mid)%limit]) <= 0)
  439.             high = mid;
  440.         else
  441.             low = mid + 1;
  442.     }
  443.     if ((ok = atIns(high,D)) != voiD0)
  444.         curNode = high;
  445.     /*  atIns() resets sorted to zero  */
  446.     flags |= BDR_SORTED;
  447.     return ok;
  448. }
  449.  
  450. voiD Binder::del()
  451. {
  452.     voiD D;
  453.     unsigned n;
  454.  
  455.     if ((D = atDel(n=curNode)) != voiD0)
  456.         if (n--)
  457.             curNode = n;
  458.     return D;
  459. }
  460.  
  461. voiD Binder::next()
  462. { 
  463.     if (linkS)  {
  464.         if (curNode >= nodes)
  465.             curNode = 0;
  466.         else
  467.             curNode++;
  468.         if (curNode < nodes)
  469.             return linkS[(first+curNode)%limit];
  470.     }
  471.     return voiD0;
  472. }
  473.  
  474. voiD Binder::prev()
  475. { 
  476.     if (linkS)  {
  477.         if (curNode)  {
  478.             if (curNode > nodes)
  479.                 curNode = nodes;
  480.             curNode--;
  481.         }
  482.         else
  483.             curNode = nodes;
  484.         if (curNode < nodes)
  485.             return linkS[(first+curNode)%limit];
  486.     }
  487.     return voiD0;
  488. }
  489.  
  490. voiD Binder::findFirst(const voiD K)
  491. {
  492.     unsigned low, mid, high;
  493.     voiD D;
  494.  
  495. /*
  496.     The current node is left undefined if
  497.     anything fails, otherwise it is set to the
  498.     newly found node.
  499. */
  500.  
  501.     curNode = nodes;
  502.     if (!linkS || !K || !comparE || !nodes)
  503.         return voiD0;
  504.     if (flags & BDR_SORTED)  {
  505.         low = 0;
  506.         high = nodes;
  507.         while (low < high)  {
  508.             mid = low + ((high - low) >> 1);
  509.             if ((*comparE)(K,linkS[(first+mid)
  510.                 %limit]) <= 0)
  511.                 high = mid;
  512.             else
  513.                 low = mid + 1;
  514.         }
  515.         if (high < nodes)
  516.             if (!(*comparE)(K,linkS[(first+
  517.                 high)%limit]))
  518.                 return linkS[(first+
  519.                 (curNode = high))%limit];
  520.     }
  521.     else  {  /*  linear search!  */
  522.         while ((D = next()) != voiD0)
  523.             if (!(*comparE)(K,D))
  524.                 return D;
  525.     }
  526.     return voiD0;
  527. }
  528.  
  529. voiD Binder::findNext(const voiD K)
  530. {
  531.  
  532. /*
  533.     For sorted binders you must first call findFirst()
  534.     to insure consistent results!
  535. */
  536.  
  537.     voiD D;
  538.  
  539. /*
  540.     The current node is left undefined if
  541.     anything fails, otherwise it is set to the
  542.     newly found node.
  543. */
  544.  
  545.     if (!linkS || !K || !comparE)  {
  546.         curNode = nodes;
  547.         return voiD0;
  548.     }
  549.     while ((D = next()) != voiD0)
  550.         if (!(*comparE)(K,D))
  551.             return D;
  552.         else if (flags & BDR_SORTED)  {
  553.             curNode = nodes;
  554.             break; /*  Look no further!  */
  555.         }
  556.     return voiD0;
  557. }
  558.  
  559. voiD Binder::findLast(const voiD K)
  560. {
  561.     unsigned low, mid, high;
  562.     voiD D;
  563.  
  564. /*
  565.     The current node is left undefined if
  566.     anything fails, otherwise it is set to the
  567.     newly found node.
  568. */
  569.  
  570.     curNode = nodes;
  571.     if (!linkS || !K || !comparE || !nodes)
  572.         return voiD0;
  573.     if (flags & BDR_SORTED)  {
  574.         low = 0;
  575.         high = nodes;
  576.         while (low < high)  {
  577.             mid = low + ((high - low) >> 1);
  578.             if ((*comparE)(K,linkS[(first+mid)
  579.                 %limit]) < 0)
  580.                 high = mid;
  581.             else
  582.                 low = mid + 1;
  583.         }
  584.         if (high < nodes)
  585.             if (!(*comparE)(K,linkS[(first+
  586.                 high)%limit]))
  587.                 return linkS[(first+
  588.                 (curNode = high))%limit];
  589.     }
  590.     else  {  /*  linear search!  */
  591.         while ((D = prev()) != voiD0)
  592.             if (!(*comparE)(K,D))
  593.                 return D;
  594.     }
  595.     return voiD0;
  596. }
  597.  
  598. voiD Binder::findPrev(const voiD K)
  599. {
  600.  
  601. /*
  602.     For sorted binders you must first call findLast()
  603.     to insure consistent results!
  604. */
  605.  
  606.     voiD D;
  607.  
  608. /*
  609.     The current node is left undefined if
  610.     anything fails, otherwise it is set to the
  611.     newly found node.
  612. */
  613.  
  614.     if (!linkS || !K || !comparE)  {
  615.         curNode = nodes;
  616.         return voiD0;
  617.     }
  618.     while ((D = prev()) != voiD0)
  619.         if (!(*comparE)(K,D))
  620.             return D;
  621.         else if (flags & BDR_SORTED)  {
  622.             curNode = nodes;
  623.             break; /*  Look no further!  */
  624.         }
  625.     return voiD0;
  626. }
  627.  
  628. int   Binder::sort(BDRcomparE comparE)
  629. {
  630.     unsigned low, mid, high;
  631.     unsigned d;
  632.     voiD D;
  633.  
  634. /*
  635.     The current node is always reset to undefined
  636.     regardless of the outcome of sort.
  637. */
  638.  
  639.     curNode = nodes;
  640.     if (flags & BDR_SORTED)  {
  641.         if (this->comparE == comparE || !comparE)
  642.             return 1;
  643.     }
  644.     else if (!this->comparE && !comparE)
  645.         return 0;
  646.     if (comparE)  {
  647.         this->comparE = comparE;
  648.         flags &= ~BDR_SORTED;
  649.     }
  650.     if (!nodes)
  651.         return (flags |= BDR_SORTED);
  652.     if (!linkS)
  653.         return 0;
  654.     if (first)  { /* form contiguous block at front */
  655.         d = (first + nodes) % limit;
  656.         if (d > first)
  657.             memmove(linkS,&linkS[first],
  658.                 sizeof(linkS[0])*nodes);
  659.         else if (d < first)
  660.             memmove(&linkS[d],&linkS[first],
  661.                 sizeof(linkS[0])
  662.                 *(limit-first));
  663.         /* else array is full/contiguous */
  664.         first = 0;
  665.     }
  666.     for (high = d = 1; d < nodes; high = ++d)  {
  667.         low = 0;
  668.         D = linkS[d];
  669.         while (low < high)  {
  670.             mid = low + ((high - low) >> 1);
  671.             if ((*this->comparE)(D,
  672.                 linkS[mid]) <= 0)
  673.                 high = mid;
  674.             else
  675.                 low = mid + 1;
  676.         }
  677.         if (high < d)  {
  678.             memmove(&linkS[high+1],&linkS[high],
  679.                 sizeof(linkS[0])*(d-high));
  680.             linkS[high] = D;
  681.         }
  682.     }
  683.     return (flags |= BDR_SORTED);
  684. }
  685.